package org.example.symbol;


import java.util.ArrayDeque;
import java.util.Queue;

public class BinaryTree<Key extends Comparable<Key>, Value> {

    public class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public Key key;
        public Value value;

        public TreeNode(Key key, Value value, TreeNode left, TreeNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    private TreeNode root;
    private int N;

    public BinaryTree() {
        root = null;
        N = 0;
    }

    public int size() {
        return N;
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    private TreeNode put(TreeNode root, Key key, Value value) {
        if (root == null) {
            N++;
            return new TreeNode(key, value, null, null);
        }
        if (key.compareTo(root.key) > 0) {
            root.right = put(root.right, key, value);
        } else if (key.compareTo(root.key) < 0) {
            root.left = put(root.left, key, value);
        } else {
            root.value = value;
        }
        return root;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(TreeNode x, Key key) {
        if (x == null) {
            return null;
        }
        if (key.compareTo(x.key) > 0) {
            return get(x.right, key);
        } else if (key.compareTo(x.key) < 0) {
            return get(x.left, key);
        } else {
            return x.value;
        }
    }

    public void delete(Key key) {
        delete(root, key);
    }

    private TreeNode delete(TreeNode x, Key key) {

        if (x == null) {
            return null;
        }

        if (key.compareTo(x.key) > 0) {
            x.right = delete(x.right, key);
        } else if (key.compareTo(x.key) < 0) {
            x.left = delete(x.left, key);
        } else {
            N--;
            if (x.left == null) {
                return x.left;
            }

            if (x.right == null) {
                if (x.left.right == null) {
                    return x.left;
                } else {
                    TreeNode mini = x.left.right;
                    while (x.right != null) {
                        mini = x.right;
                    }
                    return mini;
                }
            }

            TreeNode min = x.right;
            while (min.left != null) {
                min = min.left;
            }

            TreeNode n = x.right;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }

            min.left = x.left;
            min.right = x.right;
            x = min;

        }
        return x;
    }

    public Queue<Key> preErgodic() {
        Queue<Key> keys = new ArrayDeque<>();
        preErgodic(root, keys);
        return keys;
    }

    //先序遍历
    private void preErgodic(TreeNode temp, Queue<Key> keys) {
        if (temp == null) {
            return;
        }

        keys.offer(temp.key);
        if (temp.left != null) {
            preErgodic(temp.left, keys);
        }
        if (temp.right != null) {
            preErgodic(temp.right, keys);
        }
    }

    //中序遍历
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new ArrayDeque<>();
        midErgodic(root, keys);
        return keys;
    }

    private void midErgodic(TreeNode temp, Queue<Key> keys) {
        if (temp == null) {
            return;
        }
        if (temp.left != null) {
            midErgodic(temp.left, keys);
        }
        keys.offer(temp.key);
        if (temp.right != null) {
            midErgodic(temp.right, keys);
        }
    }

    //后序遍历
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new ArrayDeque<>();
        afterErgodic(root, keys);
        return keys;
    }

    private void afterErgodic(TreeNode temp, Queue<Key> keys) {
        if (temp == null) {
            return;
        }

        if (temp.left != null) {
            afterErgodic(temp.left, keys);
        }
        if (temp.right != null) {
            afterErgodic(temp.right, keys);
        }
        keys.offer(temp.key);
    }

    //层序遍历
    public Queue<Key> layerErgodic() {
        Queue keys = new ArrayDeque();
        Queue nodes = new ArrayDeque();

        nodes.offer(root);
        while (!nodes.isEmpty()) {
            TreeNode n = (TreeNode) nodes.poll();
            keys.offer(n.key);
            if (n.left != null) {
                nodes.offer(n.left);
            }
            if (n.right != null) {
                nodes.offer(n.right);
            }
        }
        return keys;
    }

    //深度计算
    public int maxDepth() {
        return maxDepth(root);
    }

    private int maxDepth(TreeNode n) {
        if (n == null) {
            return 0;
        }
        int maxl = 0;
        int maxr = 0;
        int max = 0;
        if (n.left != null) {
            maxl = maxDepth(n.left);
        }
        if (n.right != null) {
            maxr = maxDepth(n.right);
        }
        max = maxl > maxr ? maxl + 1 : maxr + 1;
        return max;
    }
}
